
class Solution1 {
    public void mergeSort(int[] nums, int begin, int end) {
        if(begin >= end) return;
        int mid = (end+begin)/2;

        mergeSort(nums,begin,mid);
        mergeSort(nums,mid+1,end);

        int []tmp = new int[end-begin+1];
        int left = begin,right = mid+1, i = 0;
        while(left<=mid&&right<=end) {
            if(nums[left]>=nums[right]) {
                tmp[i++] = nums[right++];
            }else {
                tmp[i++] = nums[left++];
            }
        }
        while(left<=mid) {
            tmp[i++] = nums[left++];
        }
        while(right<=end) {
            tmp[i++] = nums[right++];
        }

        for(int j = begin; j<=end; j++) {
            nums[j] = tmp[j-begin];
        }
    }
    public int[] sortArray(int[] nums) {
        mergeSort(nums,0,nums.length);
        return nums;
    }
}

class Solution2 {
    public int reversePairs(int[] record) {
        int ret = 0;
        for(int i = 0; i<record.length; i++) {
            for(int j = i+1; j<record.length; j++) {
                if(record[i] > record[j]) {
                    ret++;
                }
            }
        }
        return ret;
    }
}

// 升序版
class Solution3 {
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return mergeSort(nums,0,n-1);
    }

    public int mergeSort(int[] nums,int left,int right) {
        if(left >= right) return 0;
        int ret = 0;
        //选择一个中间点, 将数组划分成两部分
        int mid = (left + right) / 2;
        // [left, mid] [mid+1, right]

        //左半部分的个数 + 排序 + 右半部分的个数 + 排序
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid+1,right);

        //一左一右的个数
        int cur1 = left, cur2 = mid+1, i = 0;
        while(cur1<=mid && cur2 <= right) {
            if(nums[cur1] <= nums[cur2]) {
                tmp[i++] = nums[cur1++];
            }else {
                ret += mid-cur1+1;
                tmp[i++] = nums[cur2++];
            }
        }

        // 处理一下排序
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];
        for(int j = left; j<=right; j++) {
            nums[j] = tmp[j-left];
        }

        return ret;
    }
}

//降序版

class Solution {
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return mergeSort(nums,0,n-1);
    }

    public int mergeSort(int[] nums,int left,int right) {
        if(left >= right) return 0;
        int ret = 0;
        //选择一个中间点, 将数组划分成两部分
        int mid = (left + right) / 2;
        // [left, mid] [mid+1, right]

        //左半部分的个数 + 排序 + 右半部分的个数 + 排序
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid+1,right);

        //一左一右的个数
        int cur1 = left, cur2 = mid+1, i = 0;
        while(cur1<=mid && cur2 <= right) {
            if(nums[cur1] <= nums[cur2]) {
                tmp[i++] = nums[cur2++];
            }else {
                ret += right - cur2 +1;
                tmp[i++] = nums[cur1++];
            }
        }

        // 处理一下排序
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];
        for(int j = left; j<=right; j++) {
            nums[j] = tmp[j-left];
        }

        return ret;
    }
}

public class Test {
    public static void main(String[] args) {
        int[] nums = {9, 7, 5, 4, 6};
        int ret = new Solution().reversePairs(nums);
        System.out.println(ret);
    }
}
